home *** CD-ROM | disk | FTP | other *** search
/ Visual Basic Controls / Visual Basic Controls.iso / vbcontrol / sgrege_1 / clsregex.cpp < prev    next >
C/C++ Source or Header  |  1998-05-29  |  46KB  |  1,777 lines
  1. // Win32 porting notes.
  2.  
  3. #if defined( _MBCS )
  4. #pragma message( __FILEINFO__ "This code is broken under _MBCS, " \
  5.                  "see the comments at the top of this file." )
  6. #endif //_MBCS
  7.  
  8. //
  9. //
  10. // In case this isn't obvious from the later comments this is an ALTERED
  11. // version of the software. If you like my changes then cool, but nearly
  12. // all of the functionality here is derived from Henry Spencer's original
  13. // work.
  14. //
  15. // This code should work correctly under both _SBCS and _UNICODE, I did
  16. // start working on making it work with _MBCS but gave up after a while
  17. // since I don't need this particular port and it's not going to be as
  18. // straight forward as the other two.
  19. //
  20. // The problem stems from the compiled program being stored as TCHARS,
  21. // the individual items need to be wide enough to hold whatever character
  22. // is thrown at them, but currently they are accessed as an array of
  23. // whatever size integral type is appropriate.  _MBCS would cause this
  24. // to be char, but at times it would need to be larger.  This would
  25. // require making the program be an array of short with the appropriate
  26. // conversions used everywhere.  Certainly it's doable, but it's a pain.
  27. // What's worse is that the current code will compile and run under _MBCS,
  28. // only breaking when it gets wide characters thrown against it.
  29. //
  30. // I've marked at least one bit of code with #pragma messages, I may not
  31. // get all of them, but they should be a start
  32. //
  33. // Guy Gascoigne - Piggford (ggp@bigfoot.com) Friday, February 27, 1998
  34.  
  35.  
  36. // regcomp and regexec -- regsub and regerror are elsewhere
  37. // @(#)regexp.c    1.3 of 18 April 87
  38. //
  39. //    Copyright (c) 1986 by University of Toronto.
  40. //    Written by Henry Spencer.  Not derived from licensed software.
  41. //
  42. //    Permission is granted to anyone to use this software for any
  43. //    purpose on any computer system, and to redistribute it freely,
  44. //    subject to the following restrictions:
  45. //
  46. //    1. The author is not responsible for the consequences of use of
  47. //        this software, no matter how awful, even if they arise
  48. //        from defects in it.
  49. //
  50. //    2. The origin of this software must not be misrepresented, either
  51. //        by explicit claim or by omission.
  52. //
  53. //    3. Altered versions must be plainly marked as such, and must not
  54. //        be misrepresented as being the original software.
  55. // *** THIS IS AN ALTERED VERSION.  It was altered by John Gilmore,
  56. // *** hoptoad!gnu, on 27 Dec 1986, to add \< and \> for word-matching
  57. // *** as in BSD grep and ex.
  58. // *** THIS IS AN ALTERED VERSION.  It was altered by John Gilmore,
  59. // *** hoptoad!gnu, on 28 Dec 1986, to optimize characters quoted with \.
  60. // *** THIS IS AN ALTERED VERSION.  It was altered by James A. Woods,
  61. // *** ames!jaw, on 19 June 1987, to quash a regcomp() redundancy.
  62. // *** THIS IS AN ALTERED VERSION.  It was altered by Geoffrey Noer,
  63. // *** THIS IS AN ALTERED VERSION.  It was altered by Guy Gascoigne - Piggford
  64. // *** guy@wyrdrune.com, on 15 March 1998, porting it to C++ and converting
  65. // *** it to be the engine for the Regexp class
  66. //
  67. // Beware that some of this code is subtly aware of the way operator
  68. // precedence is structured in regular expressions.  Serious changes in
  69. // regular-expression syntax might require a total rethink.
  70.  
  71. #include "stdafx.h"
  72. #include "clsRegExp.h"
  73.  
  74. // The first byte of the regexp internal "program" is actually this magic
  75. // number; the start node begins in the second byte.
  76.  
  77. const TCHAR    MAGIC = ((TCHAR)'\234');
  78.  
  79. //#define new DEBUG_NEW
  80.  
  81. #pragma warning( disable : 4711 )    // automatic inline selected
  82.  
  83. // The "internal use only" fields in regexp.h are present to pass info from
  84. // compile to execute that permits the execute phase to run lots faster on
  85. // simple cases.  They are:
  86. //
  87. // regstart    char that must begin a match; '\0' if none obvious
  88. // reganch    is the match anchored (at beginning-of-line only)?
  89. // regmust    string (pointer into program) that match must include, or NULL
  90. // regmlen    length of regmust string
  91. //
  92. // Regstart and reganch permit very fast decisions on suitable starting
  93. // points for a match, cutting down the work a lot.  Regmust permits fast
  94. // rejection of lines that cannot possibly match.  The regmust tests are
  95. // costly enough that regcomp() supplies a regmust only if the
  96. // r.e. contains something potentially expensive (at present, the only
  97. // such thing detected is * or + at the start of the r.e., which can
  98. // involve a lot of backup).  Regmlen is supplied because the test in
  99. // regexec() needs it and regcomp() is computing it anyway.
  100.  
  101. // Structure for regexp "program".  This is essentially a linear encoding
  102. // of a nondeterministic finite-state machine (aka syntax charts or
  103. // "railroad normal form" in parsing technology).  Each node is an opcode
  104. // plus a "next" pointer, possibly plus an operand.  "Next" pointers of
  105. // all nodes except BRANCH implement concatenation; a "next" pointer with
  106. // a BRANCH on both ends of it is connecting two alternatives.  (Here we
  107. // have one of the subtle syntax dependencies: an individual BRANCH (as
  108. // opposed to a collection of them) is never concatenated with anything
  109. // because of operator precedence.)  The operand of some types of node is
  110. // a literal string; for others, it is a node leading into a sub-FSM.  In
  111. // particular, the operand of a BRANCH node is the first node of the
  112. // branch.  (NB this is *not* a tree structure: the tail of the branch
  113. // connects to the thing following the set of BRANCHes.)  The opcodes
  114. // are:
  115.  
  116. enum {
  117. //  definition    number        opnd?    meaning
  118.     END        =    0,        //    no        End of program.
  119.     BOL        =    1,        //    no        Match beginning of line.
  120.     EOL        =    2,        //    no        Match end of line.
  121.     ANY        =    3,        //    no        Match any character.
  122.     ANYOF    =    4,        //    str        Match any of these.
  123.     ANYBUT    =    5,        //    str        Match any but one of these.
  124.     BRANCH    =    6,        //    node    Match this, or the next..\&.
  125.     BACK    =    7,        //    no        "next" ptr points backward.
  126.     EXACTLY    =    8,        //    str        Match this string.
  127.     NOTHING    =    9,        //    no        Match empty string.
  128.     STAR    =    10,        //    node    Match this 0 or more times.
  129.     PLUS    =    11,        //    node    Match this 1 or more times.
  130.     WORDA    =    12,        //    no        Match "" at wordchar, where prev is nonword
  131.     WORDZ    =    13,        //    no        Match "" at nonwordchar, where prev is word
  132.     OPEN    =    20,        //    no        Sub-RE starts here.
  133.                         //            OPEN+1 is number 1, etc.
  134.     CLOSE    =    30        //    no        Analogous to OPEN.
  135. };
  136.  
  137. // Opcode notes:
  138. //
  139. // BRANCH    The set of branches constituting a single choice are hooked
  140. //        together with their "next" pointers, since precedence prevents
  141. //        anything being concatenated to any individual branch.  The
  142. //        "next" pointer of the last BRANCH in a choice points to the
  143. //        thing following the whole choice.  This is also where the
  144. //        final "next" pointer of each individual branch points; each
  145. //        branch starts with the operand node of a BRANCH node.
  146. //
  147. // BACK        Normal "next" pointers all implicitly point forward; BACK
  148. //        exists to make loop structures possible.
  149. //
  150. // STAR,PLUS    '?', and complex '*' and '+', are implemented as circular
  151. //        BRANCH structures using BACK.  Simple cases (one character
  152. //        per match) are implemented with STAR and PLUS for speed
  153. //        and to minimize recursive plunges.
  154. //
  155. // OPEN,CLOSE    ...are numbered at compile time.
  156.  
  157. // A node is one char of opcode followed by two chars of "next" pointer.
  158. // "Next" pointers are stored as two 8-bit pieces, high order first.  The
  159. // value is a positive offset from the opcode of the node containing it.
  160. // An operand, if any, simply follows the node.  (Note that much of the
  161. // code generation knows about this implicit relationship.)
  162. //
  163. // Using two bytes for the "next" pointer is vast overkill for most things,
  164. // but allows patterns to get big without disasters.
  165.  
  166.  
  167. enum
  168. {
  169.     REGERR_SENTINEL_VALUE = 0,
  170.     REGERR_NULLARG = 1, REGERR_CORRUPTED, REGERR_CORRUPTION, REGERR_CORRUPTED_POINTERS,
  171.     REGERR_BAD_REGREPEAT, REGERR_CORRUPTED_OPCODE, REGERR_NULL_TO_REGSUB,
  172.     REGERR_DAMAGED_REGEXP_REGSUB, REGERR_DAMAGED_MATCH_STRING, REGERR_NULL_TO_REGCOMP,
  173.     REGERR_TO_BIG, REGERR_TO_MANY_PAREN, REGERR_UNTERMINATED_PAREN, REGERR_UNMATCHED_PAREN,
  174.     REGERR_INTERNAL_ERROR_JUNK, REGERR_OP_COULD_BE